import java.util.ArrayList;
import java.util.List;

/*
 * @author zzr
 * @date: 2025/10/11  17:14
 * @description:
 * 杨辉三角
 */
public class Demo2 {
    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> ret = new ArrayList<>();
        // 第一行
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        ret.add(firstRow);

        // 从第二行开始，i 初始值为 1
        for (int i = 1; i < numRows; i++) {
            // 中间列
            List<Integer> curRow = new ArrayList<>();
            // 第一个元素也都是1
            curRow.add(1);
            //找到当前列的上一列
            List<Integer> preRow = ret.get(i - 1);
            // 填充中间列的中间元素
            for (int j = 1; j < i; j++) { // 第一个元素为 1 最后一个元素也为 1 所以 j 初始值为 1;j < i
                int x = preRow.get(j) + preRow.get(j - 1);
                curRow.add(x);
            }
            curRow.add(1); // 最后一个元素为 1
            ret.add(curRow);
        }
        return ret;
    }
}
